package com.captain.leetcode.链表;

import java.util.List;

/**
 * Des:
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * <p>
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 * <p>
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 * <p>
 * 输入：head = [2,1], x = 2
 * 输出：[1,2]
 *
 * @author XL
 * @Date 2021/8/11 16:00
 */
public class 分隔链表86 {

    public static void main(String[] args) {
        ListNode partition = new 分隔链表86().partition(ListNode.getInstance(), 4);
    }

    /**
     * 问题:同时操控三个链表, 有些混乱
     * 解决:弄清楚 next指针的含义
     */
    public ListNode partition(ListNode head, int x) {
        //循环筛选
        //x 小的  小链表
        //x 大的  大链表
        //小链表.next = 大链表 完事
        ListNode small = new ListNode(-1);
        //small操作链表
        ListNode curSmall = small;

        ListNode large = new ListNode(-1);
        //large操作链表
        ListNode curLarge = large;

        while (head != null) {
            if (head.val < x) {
                curSmall.next = head;
                curSmall = curSmall.next;
            } else {
                curLarge.next = head;
                curLarge = curLarge.next;
            }
            head = head.next;
        }
        curLarge.next = null;
        curSmall.next = large.next;
        return small.next;
    }
}
